1. Field of the Invention
The present invention relates to data storage devices and, in particular, to a first-in, first-out ("FIFO") memory configuration having a third memory pointer, in addition to the normal read and write memory pointers, which effectively increases the storage capacity of the FIFO with respect to multi-word messages by decreasing the otherwise normal storage requirements.
2. Description of the Prior Art
Modern data communications systems are often connected so as to form a network consisting of several data processors interconnected via common, or shared, data medium. The use of a shared data medium allows the individual processors to communicate with one another, sharing instructions and data. An example of such a shared data medium is a local area network ("LAN").
The physical embodiment of the shared data medium may consist of any of several distinct types. Perhaps the most common type (or perhaps at least the most familiar) is a hard-wired "bus" configuration where one or more copper wires, cables or lines of conductive printed circuit etch conduct electrical signals which represent the instructions and data. The wires, cables or printed circuit etch are hard-wired to the individual data processors in the network. An example of this type is the data bus typically found in virtually any ordinary computer.
Another computer type of shared data medium is an electromagnetic link where electromagnetic signals (e.g., radio frequency or microwave) represent the instructions and data. The electromagnetic signals are transmitted and received over the air or through special cables (e.g., coaxial or tri-axial cables) by the individual data processors in the network. An example of this type is called "packet radio" and involves the transmission and reception of radio frequency signals containing destination address information. When a data processor within the network receives such a signal, it examines the destination address information contained therein to determine whether that processor is the destination processor for that particular signal. If it is, the signal's information is stored and used by that processor accordingly.
Yet another type of shared data medium becoming increasingly common is an optical fiber where a fiberoptic cable carries optical signals (e.g., pulses of light) which represent the instructions and data. This fiberoptic cable is "hard-wired" to the individual data processors in the network via fiberoptic connectors. The use of an optical fiber as the shared data medium has increased because modern data communications systems have become faster and more sophisticated. An example is the optical fiber ring LAN standard called the Fiber Distributed Data Interface ("FDDI").
Particularly when many data processors are interconnected to form a large network, some or perhaps even most of the instruction and/or data signals propagating through the shared data medium are not destined for nor intended for use by some or perhaps even most of the processors. Therefore, to avoid unnecessary signal manipulation and processing and to maintain high throughput of the signals which are destined for and/or intended for use by them, the individual data processors are typically provided with the capability to examine the instructions and/or data received from the shared data medium before committing thereto and performing any extensive operations thereon. Thus, the faster a processor can examine its received instructions and/or data and determine whether they are to be retained for use or discarded, the faster the processor can accept and process new instructions and/or data.
As the signal propagation rate of the shared data medium increases, the potential signal throughput increases. As the potential signal throughput increases, the time available to each processor for examining incoming instructions and/or data before committing thereto and operating thereon decreases. Therefore, as the signal throughput increases it becomes increasingly desirable to be able to quickly examine the incoming instructions and/or data and determine whether they should be retained for processing. This ability is particularly desirable when the shared data medium is an optical fiber since the potential signal throughput is so high and all instructions and/or data must pass through the processor's interface to the optical fiber anyway.
A "ring" architecture is becoming an increasingly common network architecture for high speed data communications systems. In a ring network such as FDDI, instead of merely connecting to the shared data medium and monitoring the data as it appears on the line, accepting and storing data only as desired, each processor's interface in an FDDI ring must become a serial element within the network. In other words, each processor's interface must be part of the network, serving as a data repeater. Each interface must be able to accept data from the network and immediately retransmit the data back into the network for examination and/or use by another processor, while at the same time, temporarily store the data, examine the data to see if it is intended for use by that particular processor, and copy and store the data if it is so intended.
Typically, this is done through the use of a data repeater register and a first-in, first-out ("FIFO") memory configuration within each processor's interface. The interface accepts and stores ("writes") data within both the data repeater register and the FIFO memory in the order in which it has been received. While data is being copied into the interface's FIFO, the interface examines the data and determines whether or not the data is to remain for use within that processor, or is to simply be discarded. If the data is not to remain and be used within that processor, the data within the FIFO memory is discarded (e.g., overwritten by subsequent inputted data). Meanwhile, the received data is immediately retransmitted into the network by the repeater register and continues to propagate through the shared data medium of the network.
This requisite capability for storing and examining data requires that the FIFO be at least as large as the longest subgroup of data (e.g., "header") within each group of data (e.g., "frame") that must be examined for deciding whether to copy and store the data. The reason for this is that typically the entire header (e.g., address fields) of the frame is examined before the decision is made to retain or discard the data. The point in the incoming data stream for this decision to retain or discard the data is called the "commit point," and it is often unknown where the commit point is in any given data frame. For some data frames, the commit point may be at the end of the frame, i.e., after all data has been received and written into the FIFO.
Furthermore, since the central processing unit ("CPU") within the data processor may be busy and unable to use the data immediately upon its initial storage, the FIFO should be even larger than the largest header in order to retain up to one full header for examination while completing the transfer of a previously received frame to the processor's main memory and/or CPU. Moreover, the data retained for use by the processor should be protected from being overwritten until it is no longer needed. This could easily require the use of a FIFO which would be so large, complex and expensive as to be economically unfeasible, or a FIFO which would need so many associated memory circuits as to be economically undesirable.
An example of a FIFO memory configuration potentially operable within such a data repeater within a LAN is described by Fraser, U.S. Pat. No. 4,507,760. Fraser's FIFO includes the usual "read" and "write" memory pointers, which are well known in the art. The read pointer "points" to the memory location from which data was last retrieved. As outgoing data is sequentially retrieved from the FIFO, the read pointer advances within the FIFO. The write pointer points to the memory location into which data was last stored. As incoming data is sequentially stored, the write pointer advances within the FIFO.
Fraser's FIFO configuration adds a third memory pointer which is used to point to the memory location wherein the last data word (e.g., byte) of the incoming data frame has been stored. However, Fraser's third memory pointer may only be used to indicate the end of a frame, and then only if the entire frame has been determined to have been received error-free. Thus, Fraser's FIFO configuration with a third memory pointer offers no advantages or capabilities with respect to demarcating between received data which is to be retained and used and data which is to merely be aborted, until the complete frame has been received and validated.
Therefore, there is a need for an economically feasible FIFO memory configuration which provides for selective retention and protection of received data, while also providing adequate unprotected storage capacity for further incoming data.